package advanced.class03;

public class Test {

    public static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int data) {
            this.value = data;
        }
    }

    // 打印莫里斯遍历的过程
    public void Morris(TreeNode root){
        if(root == null) return;
        TreeNode cur1 = root;
        TreeNode cur2 = null;
        while(cur1 != null){
            cur2 = cur1.left;
            if(cur2 != null){
                while(cur2.right != null && cur2.right != cur1){
                    cur2 = cur2.right;
                }
                if(cur2.right == null){
                    cur2.right = cur1;
                    System.out.println(cur1.value);
                    cur1 = cur1.left;
                    continue;
                }else{
                    cur2.right = null;
                }
            }
            System.out.println(cur1.value);
            cur1 = cur1.right;
        }
    }

    // Morris前序遍历
    public void preMorris(TreeNode root){
        if(root == null) return;
        TreeNode cur1 = root;
        TreeNode cur2 = null;
        while(cur1 != null){
            cur2 = cur1.left;
            if(cur2 != null){
                while(cur2.right != null && cur2.right != cur1){
                    cur2 = cur2.right;
                }
                if(cur2.right == null){
                    cur2.right = cur1;
                    System.out.println(cur1.value);
                    cur1 = cur1.left;
                    continue;
                }else{
                    cur2.right = null;
                }
            }else{
                System.out.println(cur1.value);
            }
            cur1 = cur1.right;
        }
    }

    // Morris中序遍历
    // 中序遍历只有方法cur2右移的时候才打印
    public void midMorris(TreeNode root){
        if(root == null) return;
        TreeNode cur1 = root;
        TreeNode cur2 = null;
        while(cur1 != null){
            cur2 = cur1.left;
            if(cur2 != null){
                while(cur2.right != null && cur2.right != cur1){
                    cur2 = cur2.right;
                }
                if(cur2.right == null){
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    continue;
                }else{
                    cur2.right = null;
                }
            }
            System.out.println(cur1.value);
            cur1 = cur1.right;
        }
    }

    // Morris后序遍历
    // 中序遍历只有方法cur2右移的时候才打印
    public void posMorris(TreeNode root){
        if(root == null) return;
        TreeNode cur1 = root;
        TreeNode cur2 = null;
        while(cur1 != null){
            cur2 = cur1.left;
            if(cur2 != null){
                while(cur2.right != null && cur2.right != cur1){
                    cur2 = cur2.right;
                }
                if(cur2.right == null){
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    continue;
                }else{
                    cur2.right = null;
                    printEdge(cur1.left);
                }
            }
            cur1 = cur1.right;
        }
    }

    // 打印整条边
    private void printEdge(TreeNode head) {
        // 首先将head所在的边逆序
        TreeNode re = reverse(head);
        TreeNode cur = re;
        while(cur != null){
            System.out.println(cur.value);
            cur = cur.right;
        }
        reverse(re);
    }

    // 反转当前的二叉树
    private TreeNode reverse(TreeNode node){
        TreeNode pre = null;
        TreeNode next = null;
        while (node != null) {
            next = node.right;
            node.right = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
}
